#include<iostream>
#include<unordered_map>


using namespace std;

//1.双向链表用于添加和删除
struct DLinkNode
{
    int key;
    int value;
    DLinkNode* prev;
    DLinkNode* next;
    //构造函数
    DLinkNode():key(0),value(0),prev(nullptr),next(nullptr){}
    DLinkNode(int _key,int _value):key(_key),value(_value),prev(nullptr),next(nullptr){}
};


class LRUcache{
    private:
        // 2. 私有成员变量
        unordered_map<int,DLinkNode* > cache;
        DLinkNode* head; //最近使用
        DLinkNode* tail; //最久未使用
        int size;
        int capacity;

    // 3. 辅助函数：添加节点到链表头部
    void addToHead(DLinkNode* node){
        node->prev=head;
        node->next=head->next;
        head->next->prev=node;
        head->next=node;
    }
    
    //4.移除节点
    void removeNode(DLinkNode* node){
        node->prev->next=node->next;
        node->next->prev=node->prev;
    }

    //5.移动节点到链表头部
    void moveToHead(DLinkNode* node){
        removeNode(node);
        addToHead(node);
    }

    //6.移除尾节点并返回该节点
    DLinkNode* removeTail(){
        DLinkNode* node=tail->prev;
        removeNode(node);
        return node;
    }

    public:
        //7 构造函数
        LRUcache(int _capacity):capacity(_capacity),size(0){
            head=new DLinkNode();
            tail=new DLinkNode();
            head->next=tail;
            tail->prev=head;
        }

        //8 Get:如果key存在，获取值并移动到头部
        int get(int key){
            if(cache.find(key)==cache.end()){
                return -1;
            }
            DLinkNode* node=cache[key];
            moveToHead(node);
            return node->value;
        }

        //9 Put:插入或者更新值
        void put(int key,int value){
            if(cache.find(key)==cache.end()){
                DLinkNode* node=new DLinkNode(key,value);
                cache[key]=node;
                addToHead(node);
                size++;
                if(size>capacity){
                    DLinkNode* node=removeTail();
                    cache.erase(node->key);
                    delete node;
                    size--;
                }
            }
            else{
                DLinkNode* node=cache[key];
                node->value=value;
                moveToHead(node);
            }
        }

        //10 析构
        ~LRUcache(){
            DLinkNode* cur=head->next;
            while(cur!=tail){
                DLinkNode* tmp=cur;
                cur=cur->next;
                delete tmp;
            }
            delete head;
            delete tail;
        }

};





#include <iostream>
#include <assert.h> 

void runTests() {
    std::cout << "Running Test Case 1..." << std::endl;
    // Test Case 1 代码...
    LRUcache cache(2);
    cache.put(1, 1);
    cache.put(2, 2);
    cout << cache.get(1) << endl;    // 预期输出: 1
    cout << cache.get(2) << endl;    // 预期输出: 2
    cout << cache.get(3) << endl;    // 预期输出: -1 (key不存在)
    std::cout << "Running Test Case 2..." << std::endl;

    // Test Case 2 代码...
    LRUcache cache2(2);
    cache2.put(1, 1);
    cache2.put(2, 2);
    cache2.put(3, 3); // 缓存已满，此操作应驱逐 key=1 (最久未使用)
    cout << cache2.get(1) << endl;    // 预期输出: -1 (已被驱逐)
    cout << cache2.get(2) << endl;    // 预期输出: 2
    cout << cache2.get(3) << endl;    // 预期输出: 3
    
    std::cout << "Running Test Case 3..." << std::endl;
    // Test Case 3
    LRUcache cache3(2);
    cache3.put(1, 1);
    cache3.put(2, 2);
    cout << cache3.get(1) << endl;    // 预期输出: 1 (访问key=1，使其变为MRU)
    cache3.put(3, 3);                 // 缓存已满，此操作应驱逐 key=2 (现在它是LRU)
    cout << cache3.get(2) << endl;    // 预期输出: -1 (已被驱逐)
    cout << cache3.get(1) << endl;    // 预期输出: 1
    cout << cache3.get(3) << endl;    // 预期输出: 3

    std::cout << "Running Test Case 4..." << std::endl;
    // Test Case 4
    LRUcache cache4(2);
    cache4.put(1, 1);
    cache4.put(2, 2);
    cache4.put(1, 10); // 更新key=1的值，并将其变为MRU
    cout << cache4.get(1) << endl;    // 预期输出: 10 (值已更新)
    cache4.put(3, 3);                 // 缓存已满，应驱逐 key=2 (LRU)
    cout << cache4.get(2) << endl;    // 预期输出: -1
    cout << cache4.get(1) << endl;    // 预期输出: 10
    cout << cache4.get(3) << endl;    // 预期输出: 3
    std::cout << "All tests passed!" << std::endl;
 }

int main() {
    runTests();
    return 0;
}
